import java.util.Random;

public class 归并排序 {

    private static void subSort(int s, int m, int t, int[] a) {
        int[] tmp = new int[t - s + 1];
        int i = s, j = m, k = 0;
        while (i < m && j <= t) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }
        while (i < m) {
            tmp[k++] = a[i++];
        }
        while (j <= t) {
            tmp[k++] = a[j++];
        }
        System.arraycopy(tmp, 0, a, s, tmp.length);
    }

    private static void sort(int s, int len, int[] ints) {
        int size = ints.length;
        int mid = size / (len << 1);
        int c = size & ((len << 1) - 1);
        //　-------归并到只剩一个有序集合的时候结束算法-------//
        if (mid == 0)
            return;
        //　------进行一趟归并排序-------//
        for (int i = 0; i < mid; ++i) {
            s = i * 2 * len;
            subSort(s, s + len, (len << 1) + s - 1, ints);
        }
        //　-------将剩下的数和倒数一个有序集合归并-------//
        if (c != 0)
            subSort(size - c - 2 * len, size - c, size - 1, ints);
        //　-------递归执行下一趟归并排序------//
        sort(0, 2 * len, ints);
    }

    private static final int N = 100;
    public static void main(String[] args) {
        int[] ints = new int[N];
        int len = ints.length;
        Random random = new Random();
        for (int i = 0; i < len; i++) {
            ints[i] = random.nextInt(N);
        }
        int[] a = new int[]{6,3,5,9,1,8,2};
        Long start = System.currentTimeMillis();
        sort(0, 1, a);
        Long end = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder("");
        for (int i : a) {
            sb.append(i).append(", ");
        }
        System.out.println((end - start) + " ms\n[" + sb.delete(sb.length() - 2, sb.length()) + "]");
    }
}
